package com.example.leetdemo.finash;

import java.util.ArrayList;
import java.util.List;

public class Solution623 {

    public TreeNode addOneRow(TreeNode root, int val, int depth) {
        //层次遍历
        if (depth == 1) {
            return new TreeNode(val, root, null);
        }
        List<TreeNode> list = new ArrayList<>();
        list.add(root);
        int l = 1;
        while (list.size() > 0) {
            if (l == depth - 1) {
                for (int i = 0; i < list.size(); i++) {
                    if (list.get(i) != null) {
                        list.get(i).left = new TreeNode(val, list.get(i).left, null);
                        list.get(i).right = new TreeNode(val, null, list.get(i).right);
                    }
                }
                break;
            } else {
                List<TreeNode> temp = new ArrayList<>();
                for (int i = 0; i < list.size(); i++) {
                    if (list.get(i) != null) {
                        temp.add(list.get(i).left);
                        temp.add(list.get(i).right);
                    }
                }
                list = temp;
            }
            l++;
            if (l >= depth) {
                break;
            }
        }
        return root;
    }

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
